package com.mlh.dp.old;

// 题目：给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
// 你可以对一个单词进行如下三种操作：
// 插入一个字符
// 删除一个字符
// 替换一个字符

// 举例：
// 输入：word1 = "horse", word2 = "ros"
// 输出：3
// 解释：
// horse -> rorse (将 'h' 替换为 'r')
// rorse -> rose (删除 'r')
// rose -> ros (删除 'e')

public class MinDistance {
    //理解性背诵
    // 这样以来，我们就可以把原问题转化为规模较小的子问题。我们用 A = horse，B = ros 作为例子，来看一看是如何把这个问题转化为规模较小的若干子问题的。
    // 在单词 A 中插入一个字符：如果我们知道 horse 到 ro 的编辑距离为 a，那么显然 horse 到 ros 的编辑距离不会超过 a + 1。
    // 这是因为我们可以在 a 次操作后将 horse 和 ro 变为相同的字符串，只需要额外的 1 次操作，在单词 A 的末尾添加字符 s，就能在 a + 1 次操作后将 horse 和 ro 变为相同的字符串；
    // 在单词 B 中插入一个字符：如果我们知道 hors 到 ros 的编辑距离为 b，那么显然 horse 到 ros 的编辑距离不会超过 b + 1，原因同上；
    // 修改单词 A 的一个字符：如果我们知道 hors 到 ro 的编辑距离为 c，那么显然 horse 到 ros 的编辑距离不会超过 c + 1，原因同上。
    // 那么从 horse 变成 ros 的编辑距离应该为 min(a + 1, b + 1, c + 1)。


    // dp[i][j-1] 为 A 的前 i 个字符和 B 的前 j - 1 个字符编辑距离，即最少操作数
    // 即对于 B 的第 j 个字符，我们在 A 的末尾添加了一个相同的字符，那么 dp[i][j] 最小可以为 dp[i][j-1] + 1；

    // dp[i-1][j] 为 A 的前 i - 1 个字符和 B 的前 j 个字符编辑距离
    // 即对于 A 的第 i 个字符，我们在 B 的末尾添加了一个相同的字符，那么 dp[i][j] 最小可以为 dp[i-1][j] + 1；

    // dp[i-1][j-1] 为 A 前 i - 1 个字符和 B 的前 j - 1 个字符编辑距离
    // 即对于 B 的第 j 个字符，我们修改 A 的第 i 个字符使它们相同，那么 dp[i][j] 最小可以为 dp[i-1][j-1] + 1。
    // 特别地，如果 A 的第 i 个字符和 B 的第 j 个字符原本就相同，那么我们实际上不需要进行修改操作。在这种情况下，dp[i][j] 最小可以为 dp[i-1][j-1]。

    //这里面最重要的想法就是dp[i][j]可以变成dp[i][j-1]后，来处理多加位置j的字符

    //思路：dp[i][j]  含义：word1 前i个字符串可以转变成word2前j个字符的最小操作数
    public static int method1(String word1, String word2){
        char[]w1=word1.toCharArray();
        char[]w2=word2.toCharArray();
        int [][]dp=new int[w1.length+1][w2.length+1];
        if(w1.length*w2.length==0){
            return w1.length+w2.length;
        }

        //初始化数组
        for(int i=0;i<=w1.length;i++){
            dp[i][0]=i;
        }
        for(int i=0;i<=w2.length;i++){
            dp[0][i]=i;
        }

        for(int i=1;i<=w1.length;i++){
            for(int j=1;j<=w2.length;j++){
                if(w1[i-1]==w2[j-1]){
                    dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j]+1,dp[i][j-1]+1));
                }else{
                    dp[i][j]=Math.min(dp[i-1][j-1]+1,Math.min(dp[i-1][j]+1,dp[i][j-1]+1));
                }
            }
        }
        return dp[w1.length][w2.length];
    }
}
